"""
作者：赛琳伟
日期：2023年04月01日
"""
import numpy as np
import itertools


class Element:
    """群元素类"""
    def __init__(self, in_, degree=None):
        """_permut存储内容为开头0，大小为degree+1的1~degree的排列"""
        if type(in_) == str:
            deg10 = True if ' ' in in_ else False
            in_ = in_.split(')(')
            if in_[0][0] != '(':
                raise ValueError('Element init error.')
            in_[0] = in_[0][1:]
            if in_[-1][-1] != ')':
                raise ValueError('Element init error.')
            in_[-1] = in_[-1][:-1]
            p = {}
            for c in in_:
                if deg10:
                    c = [int(x) for x in c.split()]
                else:
                    c = [int(x) for x in c]
                for i in range(len(c)-1):
                    p[c[i]] = c[i+1]
                p[c[-1]] = c[0]
            if degree is None:
                degree = max(p.keys())
            self._permut = np.arange(degree+1, dtype='uint16')
            for k,v in p.items():
                self._permut[k] = v
        else:
            self._permut = np.array(in_)

    def cycle(self):
        '''计算所有的圈。不包含长度为1的'''
        result = []
        flag = np.zeros_like(self._permut)
        i = 1
        while i < len(self._permut):
            if flag[i]:
                i += 1
                continue
            c = []
            next = i
            while True:
                c.append(next)
                flag[next] = True
                next = self._permut[next]
                if next == i:
                    break
            if len(c) > 1:
                result.append(c)
            i += 1
        return result

    def __repr__(self):
        cyc = self.cycle()
        spl = ' ' if self._permut.shape[0]-1 >= 10 else ''
        s = ''.join(['(' + spl.join([str(x) for x in c]) + ')' for c in cyc])
        if not s:
            s = '(1)'
        return s

    def order(self):
        cyc = self.cycle()
        return lcm([len(c) for c in cyc])

    def __mul__(self, other):
        if self._permut.shape[0] < other._permut.shape[0]:
            self.enlarge_degree(other._permut.shape[0]-1)
        elif self._permut.shape[0] > other._permut.shape[0]:
            other.enlarge_degree(self._permut.shape[0]-1)
        return Element(self._permut[other._permut])

    def inv(self):
        result = Element(self._permut)
        result._permut[self._permut] = np.arange(self._permut.shape[0])
        return result

    def __hash__(self):
        h = 0
        base = 1
        for i in range(2, self._permut.shape[0]):
            count = np.sum(self._permut[1:i] < self._permut[i])
            count = 0
            for j in range(1, i):
                if self._permut[j] < self._permut[i]:
                    count += 1
            h += count * base
            base *= i
        return base-1-h

    def enlarge_degree(self, degree):
        if degree <= self._permut.shape[0]-1:
            return
        new_permut = np.arange(degree+1, dtype='uint16')
        new_permut[:self._permut.shape[0]] = self._permut
        self._permut = new_permut

    def n_cycle(self):
        '''长度>1的圈个数 + 长度为1的圈个数'''
        cyc = self.cycle()
        return len(cyc) + self._permut.shape[0]-1 - sum([len(c) for c in cyc])


class Group:
    """群类"""
    def __init__(self):
        self._elem = [Element([1])]
        self.hash_dict = {0:0} #元素哈希与元素下标的对应
        self.degree = 1

    def order(self):
        return len(self._elem)

    def add_element(self, e):
        h = hash(e)
        if h in self.hash_dict:
            return
        if self.degree < e._permut.shape[0]-1:
            for elem in self._elem:
                elem.enlarge_degree(e._permut.shape[0]-1)
            self.degree = e._permut.shape[0]-1
        self.hash_dict[h] = len(self._elem)
        self._elem.append(e)

    def gen(self):
        """根据当前元素生成群"""
        calc_pos = [0] * len(self._elem) #每个元素遍历相乘到的位置
        for i in itertools.count(1):
            if i >= len(self._elem):
                return len(self._elem)
            for j in itertools.count(1):
                if j >= len(self._elem):
                    break
                e = self._elem[i] * self._elem[j]
                self.add_element(e)

            for k in range(1, i):
                if calc_pos[k] < i:
                    e = self._elem[k] * self._elem[i]
                    self.add_element(e)
                    calc_pos[k] = i

            if len(calc_pos) <= i:
                calc_pos.append(0)
            calc_pos[i] = j-1

    def polya(self, m):
        """m为颜色数"""
        return sum([m**g.n_cycle() for g in self._elem]) // len(self._elem)
